import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-15
 * Time: 22:40
 */
public class Solution {

    /**
     *  从上到下  的 DP
     * @param triangle
     * @return
     */
    public static int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int row = triangle.size();
        int[][] minP = new int[row][row];
        minP[0][0] = triangle.get(0).get(0);
        // 三角形的两条腰上的最短路径都是确定的
        // 进行初始化
        for (int i = 1; i < row ; i++) {
            // j == 0  | j == i    F(i, j) = F(i-1, j) + Arr[i][j]
            minP[i][0] = minP[i-1][0] + triangle.get(i).get(0);
            minP[i][i] = minP[i-1][i-1] + triangle.get(i).get(i);
        }

        for (int i = 2; i < row ; i++) {
            // 注意这里 j < i,  而不是  j < row
            for (int j = 1; j < i ; j++) {
                // 正常情况下
                // F(i, j) = Min(F(i-1, j-1), F(i-1, j)) + Arr[i][j]
                minP[i][j] = Math.min(minP[i-1][j-1], minP[i-1][j]) + triangle.get(i).get(j);
            }
        }
        int min = minP[row-1][0];
        // 找到最低层的最小值
        for (int i = 1; i < row; i++) {
            min = Math.min(min, minP[row-1][i]);
        }
        return min;
    }


    /**
     * 从下到上的 DP
     * @param triangle
     * @return
     */
    public static int minimumTotal2(ArrayList<ArrayList<Integer>> triangle) {
        int row = triangle.size();
        int[][] minP = new int[row][row];
        // 此时初始化的就是 最后一层
        for (int i = 0; i < row; i++) {
            minP[row-1][i] = triangle.get(row-1).get(i);
        }

        for (int i = row -2; i >= 0 ; i--) {
            for (int j = 0; j <= i; j++) {
                minP[i][j] = Math.min(minP[i+1][j], minP[i+1][j+1]) + triangle.get(i).get(j);
            }
        }
        return minP[0][0];
    }



    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            lists.add(list);
        }

        lists.get(0).add(-1);
        lists.get(1).add(2);
        lists.get(1).add(3);
        lists.get(2).add(1);
        lists.get(2).add(-1);
        lists.get(2).add(-3);
        System.out.println(minimumTotal(lists));
    }
}
